package listbyorder.access001_100.test84;

import java.util.Stack;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/5 8:52
 */
public class Solution1 {

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) return 0;
        Stack<Integer> stack = new Stack<>();
        int cur_height = 0;
        int ans = 0;
        int left;
        int right;
        int len = heights.length;
        for (int i = 0; i < len;) {
            if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) {
                stack.push(i);
                i++;
            } else if (heights[i] < heights[stack.peek()]) {
                cur_height = heights[stack.pop()];
                right = i;
                left = stack.isEmpty() ? -1 : stack.peek();
                ans = Math.max((right - left - 1) * cur_height, ans);
            } else {
                i++;
            }
        }
        while (!stack.isEmpty()) {
            cur_height = heights[stack.pop()];
            right = len;
            left = stack.isEmpty() ? -1 : stack.peek();
            ans = Math.max((right - left - 1) * cur_height, ans);
        }
        return ans;
    }
}
